package com.itdfq.algorithm.recall;

/**
 * @Author: QianMo
 * @Date: 2021/11/23 9:48
 * @Description: 迷宫路线问题
 */
public class Maze {
    /**
     * 默认是false，无法行走
     */
    static boolean find = false;
    /**
     * 起始点
     */
    static int ROW = 5;
    static int COL = 5;

    public static void main(String[] args) {

        char[][] maze = new char[][]{
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '0', '1'},
                {'1', '0', '0', '1', '1'},
                {'1', '0', '0', '1', '0'},
                {'1', '0', '0', '1', '1'}};
        compute(maze, 0, 0, ROW - 1, COL - 1);
        if (find == false) {
            System.out.print("未找到可行线路");
        }

    }

    /**
     * @param arr       数组
     * @param row       起点
     * @param col
     * @param resultRow
     * @param resultCol
     */
    public static void compute(char[][] arr, int row, int col, int resultRow, int resultCol) {
        arr[row][col]='Y';
        if (row == resultRow && col == resultCol) {
            find = true;
            System.out.println("当前已经到了终点--路綫");
            printmaze(arr);
        }
        //向上
        if (canMove(arr, row - 1, col)) {
            compute(arr, row - 1, col, resultRow, resultCol);
            arr[row - 1][col] = '1';
        }
        //向下
        if (canMove(arr, row + 1, col)) {
            compute(arr, row + 1, col, resultRow, resultCol);
            arr[row + 1][col] = '1';
        }
        //向左
        if (canMove(arr, row, col - 1)) {
            compute(arr, row, col - 1, resultRow, resultCol);
            arr[row][col - 1] = '1';
        }
        //向右
        if (canMove(arr, row, col + 1)) {
            compute(arr, row, col + 1, resultRow, resultCol);
            arr[row][col + 1] = '1';
        }
    }

    //输出行走路线
    public static void printmaze(char[][] maze) {
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 尝试向上移动
     *
     * @param arr
     * @param row
     * @param col
     * @return
     */
    public static boolean canMove(char[][] arr, int row, int col) {

        if (row >= 0 && col >= 0 && row <= ROW - 1 && col <= COL - 1 && arr[row][col] == '1') {
            return true;
        } else {
            return false;
        }
    }
}
